package com.lbx.algo.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 */
public class BubbleSort {

    // 冒泡排序，a是数组，n表示数组大小
    public static void bubbleSort(int[] nums,int n){
        if(n <= 1){
            return;
        }
        for (int i=0; i<n; i++){
            for(int j=0;j< n-i-1;j++){
                if(nums[j] > nums[j+1]){
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                    System.out.println("i:"+i+"j:"+j+"==="+Arrays.toString(nums));
                }
            }
        }
    }

    // 冒泡排序，a是数组，n表示数组大小
    public static void bubbleSort1(int[] nums,int n){
        if(n <= 1){
            return;
        }
        for (int i=0; i<n; i++){
            // 提前退出标志位
            boolean flag = false;
            for(int j=0;j< n-i-1;j++){
                if(nums[j] > nums[j+1]){
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                    flag = true;
                    System.out.println("i:"+i+"j:"+j+"==="+Arrays.toString(nums));
                }
            }
            if (!flag) break;  // 没有数据交换，提前退出
        }
    }

    /**
     * 冒泡排序改进:在每一轮排序后记录最后一次元素交换的位置,作为下次比较的边界,
     * 对于边界外的元素在下次循环中无需比较.
     */
    public static void bubbleSort2(int[] nums, int n) {
        if (n <= 1) return;

        // 最后一次交换的位置
        int lastExchange = 0;
        // 无序数据的边界,每次只需要比较到这里即可退出
        int sortBorder = n - 1;
        for (int i = 0; i < n; i++) {
            // 提前退出标志位
            boolean flag = false;
            for (int j = 0; j < sortBorder; j++) {
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                    // 此次冒泡有数据交换
                    flag = true;
                    // 更新最后一次交换的位置
                    lastExchange = j;
                    System.out.println("i:"+i+"j:"+j+"==="+Arrays.toString(nums));
                }
            }
            sortBorder = lastExchange;
            if (!flag) break;    // 没有数据交换，提前退出
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{9,3, 4, 2, 1, 5, 6, 7, 8};
        bubbleSort(array, array.length);
        System.out.println("+==========================");
        array = new int[]{9,3, 4, 2, 1, 5, 6, 7, 8};
        bubbleSort1(array, array.length);
        System.out.println("+==========================");
        array = new int[]{9,3, 4, 2, 1, 5, 6, 7, 8};
        bubbleSort2(array, array.length);
    }
}
